﻿#define _CRT_SECURE_NO_WARNINGS 1

//荷兰国旗问题
//给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
//
//我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
//
//输入：nums = [2, 0, 2, 1, 1, 0]
//输出：[0, 0, 1, 1, 2, 2]

//void sortColors(int* nums, int numsSize) {
//    int n0 = 0, n1 = 0, n2 = 0;
//    for (int i = 0; i < numsSize; i++)
//    {
//        if (nums[i] == 0)
//        {
//            n0++;
//        }
//        else if (nums[i] == 1)
//        {
//            n1++;
//        }
//        else
//        {
//            n2++;
//        }
//    }
//    int i = 0;
//    for (i = 0; i < n0; i++)
//    {
//        nums[i] = 0;
//    }
//    for (; i < n0 + n1; i++)
//    {
//        nums[i] = 1;
//    }
//    for (; i < n0 + n1 + n2; i++)
//    {
//        nums[i] = 2;
//    }
//}
//快速排序的子过程 partition
void sortColors(int* nums, int numsSize) {
    int p1 = 0, p2 = numsSize - 1, i = 0;
    while (i <= p2)
    {
        if (nums[i] == 0)
        {
            int ret = nums[i];
            nums[i] = nums[p1];
            nums[p1] = ret;
            p1++;
            i++;
        }
        else if (nums[i] == 2)
        {
            int ret = nums[i];
            nums[i] = nums[p2];
            nums[p2] = ret;
            p2--;
        }
        else
        {
            i++;
        }
    }
}



//给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

//返回被除数 dividend 除以除数 divisor 得到的商。
//
//整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
//
//
//
//示例 1:
//
//输入: dividend = 10, divisor = 3
//输出 : 3
//解释 : 10 / 3 = truncate(3.33333..) = truncate(3) = 3


int my_divide(long dividend, long divisor)
{
    int x = 1;
    long ret = divisor;
    while (ret <= dividend)
    {
        ret *= divisor;
        x++;
    }
    if (x == 1)
    {
        return 0;
    }
    for (int i = ret / divisor; i >= ret / divisor / divisor; i--)
    {

        if (i * divisor <= dividend)
        {
            return i;
        }
    }
    return 0;
}

int divide(int dividend, int divisor) {
    if (dividend > 0 && divisor > 0)
    {
        return my_divide(fabs(dividend), fabs(divisor));
    }
    else if (dividend < 0 && divisor < 0)
    {
        return my_divide(fabs(dividend), fabs(divisor));
    }
    else
    {
        return -1 * my_divide(fabs(dividend), fabs(divisor));
    }
}
